/**
 * @filename BinarySearchTree.h
 * @brief BinarySearchTree
 * @author Sun Zehui <sunzehui18@outlook.com>
 * @version 1.0.0
 * @date 2021-11-23
 */
#include<iostream>
#include<vector>
#include<algorithm>
#include<random>
using namespace std;

template<typename Comparable>
class BinarySearchTree;


/**
 * @brief BST_sort 普通的二叉树排序，没有经过随即shuffle
 *
 * @tparam Comparable 可比较对象
 * @param _data 待排数据
 */
template<typename Comparable>
void BST_sort(vector<Comparable> &_data){
	BinarySearchTree<Comparable> tree;
	for(auto iter=_data.begin(); iter!=_data.end(); ++iter){
		tree.insert(*iter);
	}

	_data.clear();
	tree.inorder(_data);
}

/**
 * @brief Randomized_BST_sort 随机的二叉树排序
 *
 * @tparam Comparable 可比较对象
 * @param _data 待排数据
 */
template<typename Comparable>
void Randomized_BST_sort(std::vector<Comparable> &_data){
	shuffle(_data.begin(), _data.end(), default_random_engine(2));
	BinarySearchTree<Comparable> tree;
	for(auto iter=_data.begin(); iter!=_data.end(); ++iter){
		tree.insert(*iter);
	}

	_data.clear();
	tree.inorder(_data);
}



/**
 * @brief 二叉树类
 *
 * @tparam Comparable 可比较对象
 */
template<typename Comparable>
class BinarySearchTree
{
public:
	BinarySearchTree():root(nullptr){}
	BinarySearchTree(const BinarySearchTree& rhs): root(nullptr){
		root = clone(rhs.root);
	}
	BinarySearchTree(BinarySearchTree&& rhs):root(nullptr){
		root  = clone(std::move(rhs.root));
	}
	~BinarySearchTree(){
		makeEmpty();
	}

	/**
	 * @brief findMin 寻找最小值
	 *
	 * @return Comparable
	 */
	virtual const Comparable& findMin() const{
		findMin(root);
	}
	virtual const Comparable& findMax() const{
		findMax(root);
	}
	/**
	 * @brief contains 递归查找
	 *
	 * @param x Comparable&
	 *
	 * @return bool
	 */
	virtual bool contains(const Comparable& x) const{
		return contains(x, root);
	}
	virtual bool isEmpty() const{
		return root == nullptr;
	}
	/**
	 * @brief printTree 前序输出
	 *
	 * @param out 输出流对象
	 */
	virtual void printTree(std::ostream &out = cout) const{
		printTree(root, out);
	}

	/**
	 * @brief makeEmpty 清空内有封装的方法
	 */
	virtual void makeEmpty(){
		makeEmpty(root);
	}
	/**
	 * @brief insert 封装方法
	 *
	 * @param x Comparable&
	 */
	virtual void insert(const Comparable& x){
		insert(x, root);
	}
	virtual void insert(Comparable&& x){
		insert(std::move(x), root);
	}
	/**
	 * @brief remove 封装方法
	 *
	 * @param x Comparable&
	 */
	virtual void remove(const Comparable& x){
		remove(x, root);
	}

	/**
	 * @brief inorder 中序遍历覆盖Vector
	 *
	 * @param vec Vector<Comparable>
	 */
	virtual void inorder(vector<Comparable>& vec){
		inorder(root, vec);
	}

	virtual void preorder(vector<Comparable>& vec){
		preorder(root, vec);
	}

	virtual void postorder(vector<Comparable>& vec){
		preorder(root, vec);
	}

	/**
	 * @brief operator= 赋值复制，实现了移动语义与拷贝语义两种
	 *
	 * @param rhs rhs
	 *
	 * @return 搜索树对象
	 */
	BinarySearchTree & operator=(const BinarySearchTree& rhs){
		makeEmpty();
		root = clone(rhs.root);
	}
	BinarySearchTree & operator=(const BinarySearchTree&& rhs){
		makeEmpty();
		root = clone(std::move(rhs.root));
	}

private:
	/**
 	 * @brief Binary node struct, including pointers refering to other nodes! Has its own constructor
 	 */
	struct BinaryNode{
		Comparable element;
		BinaryNode *left;
		BinaryNode *right;

		BinaryNode(const Comparable& theElement, BinaryNode *lt, BinaryNode *rt)
			:element(theElement), left(lt), right(rt){}

		BinaryNode(Comparable&& theElement, BinaryNode *lt, BinaryNode *rt)
			:element(std::move(theElement)), left(lt), right(rt){}
	};

	BinaryNode *root;

	/**
	 * @brief insert 递归插入，不考虑重复元素
	 *
	 * @param x 对象
	 * @param t 节点
	 */
	void insert(const Comparable& x, BinaryNode * & t){
		if(t==nullptr)
			t = new BinaryNode{x, nullptr, nullptr};
		else if(x < t->element)
			insert(x, t->left);
		else if(x>t->element)
			insert(x, t->right);
		else
			; //Duplicate, Do nothing
	}
	void insert(Comparable && x, BinaryNode* & t){
		if(t==nullptr)
			t = new BinaryNode{std::move(x), nullptr, nullptr};
		else if(x<t->element)
			insert(std::move(x), t->left);
		else if(x>t->element)
			insert(std::move(x), t->right);
		else
			; //Do nothing
	}
	/**
	 * @brief remove 递归删除
	 *
	 * @param x 对象
	 * @param t 节点
	 */
	void remove(const Comparable& x, BinaryNode* & t){
		if(t==nullptr)
			return;
		else if(x<t->element)
			remove(x, t->left);
		else if(x>t->element)
			remove(x, t->right);
		else if(t->left != nullptr && t->right != nullptr){
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			BinaryNode *oldNode = t;
			t = ( t->left != nullptr ) ? t->left : t->right;
			delete oldNode;
		}
	}
	
	/**
	 * @brief findMin 递归查找最小值
	 *
	 * @param t
	 *
	 * @return Node*
	 */
	BinaryNode * findMin(BinaryNode *t) const{
		if(t == nullptr)
			return nullptr;
		if(t->left == nullptr)
			
			return t;
		return findMin(t->left);
	}

	BinaryNode * findMax(BinaryNode *t) const{
		if(t!=nullptr)
			while(t->right!=nullptr)
				t=t->right;
		return t;
	}

	/**
	 * @brief contains 递归查找
	 *
	 * @param x 对象
	 * @param t 节点
	 *
	 * @return bool，是否存在
	 */
	bool contains(const Comparable& x, BinaryNode *t) const{
		if( t == nullptr )
			return false;
		else if( x < t->element )
			return contains( x, t->left );
		else if( t->element < x )
			return contains( x, t->right );
		else
			return true;
	}
	/**
	 * @brief makeEmpty 递归清空
	 *
	 * @param t
	 */
	void makeEmpty(BinaryNode * & t){
		if(t!=nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}
	void printTree(BinaryNode* t, std::ostream& out) const{
		if( t!=nullptr ){
			printTree(t->left, out);
			out << t->element << "\t";
			printTree(t->right, out);
		}
		else
			; //Do nothing!
	}
	/**
	 * @brief clone 深拷贝
	 *
	 * @param t
	 *
	 * @return 节点指针
	 */
	BinaryNode * clone(BinaryNode* t) const{
		if( t == nullptr )
			return nullptr;
		else
			return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
	}

	/**
	 * @brief inorder 中序遍历的递归表达
	 *
	 * @param t 节点
	 * @param vec Vector<Comparable>
	 */
	void inorder(BinaryNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			inorder(t->left, vec);
			vec.push_back(t->element);
			inorder(t->right, vec);
		}
	}

	void preorder(BinaryNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			vec.push_back(t->element);
			inorder(t->left, vec);
			inorder(t->right, vec);
		}
	}

	void postorder(BinaryNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			inorder(t->left, vec);
			inorder(t->right, vec);
			vec.push_back(t->element);
		}
	}

};
